\documentclass[10pt,journal,letterpaper,compsoc]{IEEEtran}

\usepackage{multirow}
\usepackage{graphics}
\usepackage{epsfig}
\usepackage{helvet}
\usepackage{courier}
\usepackage{color}
\usepackage{array}
\usepackage{enumerate}
\usepackage{subfigure,fancyvrb}
\usepackage[vlined,ruled]{algorithm2e}
\usepackage{colordvi,epsfig,multirow,amsmath,amssymb}
%\usepackage{natbib}

\newtheorem{defi}{Definition}
\newtheorem{thm}{Theorem}
\newcommand{\nop}[1]{}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}

\DeclareMathOperator*{\argmin}{arg\,min}

\ifCLASSOPTIONcompsoc
  % \usepackage[nocompress]{cite}
\else
  % \usepackage{cite}
\fi

% *** GRAPHICS RELATED PACKAGES ***
\ifCLASSINFOpdf
\else
\fi

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

\begin{document}

\title{QoS-driven Dynamic Composition of Web Services using SAT-based Temporal Planning}

\author{Guobing~Zou,
        Yixin~Chen,~\IEEEmembership{Senior Member,~IEEE,}
        Qiang Lu, Ruoyun~Huang, You Xu,
        and~Yang Xiang

\IEEEcompsocitemizethanks{
\IEEEcompsocthanksitem G. Zou is with the Department of Computer Science and Engineering,\protect\\ Washington University, MO 63130, USA.\protect\\
Tongji University, Shanghai 201804, China.\protect\\
E-mail: guobingzou@gmail.com \vspace{0.5mm}
\IEEEcompsocthanksitem Y. Chen, R. Huang and Y. Xu are with the Department of Computer Science and Engineering, Washington University, MO 63130, USA.\protect\\
E-mail: \{chen, rh11, yx2\}@cse.wustl.edu \vspace{0.5mm}
\IEEEcompsocthanksitem Q. Lu is with the Department of Computer Science and Engineering, University of Science and Technology of China, Hefei 230026, China.\protect\\
E-mail: rczx@mail.ustc.edu.cn \vspace{0.5mm}
\IEEEcompsocthanksitem Y. Xiang is with the Department of Computer Science and Technology,\protect\\ Tongji University, Shanghai 201804, China. \protect\\
E-mail: shxiangyang@tongji.edu.cn}
\thanks{}}

% The paper headers
\markboth{IEEE Transactions on Services Computing,~Vol.~4, No.~3, July-September~2011}%
{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for Computer Society Journals}

\IEEEcompsoctitleabstractindextext{%
\begin{abstract}
Web service composition is the task of combining a chain of connected single services together to create a more complex and value-added composite service. Quality of Service (QoS) has been mostly applied to represent nonfunctional properties of Web services and differentiate those with the same functionality. Many research has been done on QoS-aware service composition problem, as it significantly affects the quality of a composite service. However, existing methods are restricted on predefined workflows, which can incur a couple of limitations, such as lack of guarantee for the optimality on overall QoS and for the completeness of finding a composite service solution. In this paper, instead of predefining a workflow model for service selection, we propose a novel planning-based approach that can automatically convert a QoS-aware composition task to a numeric planning problem. Furthermore, we use state-of-the-art numeric planners, including an existing one and a self-developed one, to handle complex temporal planning problems with numeric reasoning. Our approach can find a composite service solution with optimal overall QoS score while satisfying multiple global QoS constraints. We implement a prototype and conduct extensive experiments on large Web service repositories. The experimental results show that our proposed approach outperforms existing ones in its overall QoS score of a composite service solution.
\end{abstract}

\begin{IEEEkeywords}
Web services, service composition, QoS, automated planning, satisfiability.
\end{IEEEkeywords}}

\maketitle
\IEEEdisplaynotcompsoctitleabstractindextext
\IEEEpeerreviewmaketitle

\section{Introduction}

%paragraph I: Web services

\IEEEPARstart{W}{eb} services are modular, self-describing, self-contained, platform-independent software components that can be published by service providers and consumed by service requesters over the Internet. Recently, Web services technique is one of the most important developments under the Service-Oriented Architecture (SOA), allowing the construction and sharing of independent and autonomous softwares \cite{El10}. Several off-the-shelf stack of languages and protocols have been employed to describe and publish Web services, such as WSDL and UDDI, as well as to support mutual communication among Web services, such as SOAP. Since Web services have been widely recognized as basic components to dynamically build distributed applications, many individuals or organizations prefer to only keep their principal business, but outsource other application services over the Internet \cite{Rao05}.

%paragraph II: QoS driven Web services composition

When the users submit a service request to a service repository, in many cases there is no single Web service that provides the capability to satisfy that request. Web service composition (WSC) is the task of combining a set of single Web services together to create a more complex, value-added and cross-organizational business process. Within a composite service, each single Web service is responsible to perform a specific functionality. However, there are a couple of research challenges in Web service composition. First, how to rapidly select a group of Web services for a composite service that can satisfy a service request has become a challenge, as the number of component services involved in a composite service tends to be very large, and the number of services from which these component services are selected is likely to be even larger \cite{Zeng04}. For those Web services providing the same functionality, Quality of Service (QoS) has been mostly applied to represent their nonfunctional properties and differentiate them for service selection. QoS is a broad concept that encompasses a number of nonfunctional properties, such as execution price, execution duration, availability, execution success rate and reputation \cite{Zeng04}. Second, given a set of global QoS constraints and preferences set by the users, the challenge is that how to efficiently construct a composite service such that its overall QoS score is optimal, while all the global QoS constraints are satisfied.

%paragraph III: Traditional QoS driven Web services composition model

Existing QoS-aware Web service composition methods are restricted to predefined workflows. That is, in order to provide a composite service, it must have a predefined workflow model to support service selection, as the one shown in Fig. \ref{fig:qos-workflow}. A predefined workflow consists of a set of tasks. For each task in a workflow, it corresponds to a group of candidate Web services so that each of them can perform the task. Fig. \ref{fig:qos-candidate-ws} illustrates the candidate services for a workflow model with $p$ tasks. As a result, the conventional QoS-aware Web service composition approaches \cite{Zeng04,Menasce04,Jaeger04,Zhang07,Wu07,Hwang08} work with a predefined workflow model. They select one service for each task from its corresponding candidate services set, with an aim to optimize the QoS score and satisfy the QoS constraints. However, the conventional approaches have made a strong assumption: the workflow is given and fixed. This may incur two limitations. One is that even though these approaches can find a composite service, they can not make sure its overall QoS is optimal, considering other workflows. Another limitation is that these approaches do not guarantee to find a solution satisfying the global QoS constraints, even if there exists one under a different workflow.

%\vspace{-1mm}
\begin{figure}[tp]
    \centering
    \includegraphics[scale=0.68]{figure/wsc-workflow-8.eps}
    \centering
    \caption {\small A predefined workflow model for a Web service composition. It consists of 8 business process tasks.}
\label{fig:qos-workflow}
\end{figure}
%\vspace{-1mm}

\begin{figure}[tp]
    \centering
    \includegraphics[scale=0.66]{figure/tradition-model.eps}
    \centering
    \caption {\small The candidate services for a composite service workflow model containing $p$ tasks. For each task $t_i (1 \leq i \leq p)$, it corresponds to a set of candidate services $T_i$.}
\label{fig:qos-candidate-ws}
\vspace{-6mm}
\end{figure}

%\newpage
Automated planning is a popular method for Web service composition \cite{Falou10,Bertoli09,Hoffmann09,Oh08,Zheng08,Hoffmann07,Oh07,Pistore05,Pistore05a,
Sirin04}. However, these approaches only try to find a composite service satisfying the functionality requirement, but do not take QoS into account. Therefore, although many works have been done for Web service composition using planning, designing an approach considering QoS constraints and preferences remains a challenging open problem.

Our goal is to optimize the overall QoS and satisfy the QoS constraints. However, finding optimal solutions without a predefined workflow is very challenging, because it is a very difficult optimization problem with discrete decisions, temporal constraints, and numeric reasoning. In particular, when the number of Web services is large, there is a huge search space.

%paragraph IV: Our proposed framework using planning

In this paper, we propose a novel planning-based approach for dynamic composition of Web services with QoS support. Users can specify global QoS constraints and preferences, and our approach aims to find the composition solution that optimizes the overall QoS score and satisfies the QoS constraints.

Instead of predefining a workflow model for the selection of Web service composition, our approach transforms a composition task together with global QoS constraints and preferences to a planning problem with temporal and numeric features. Depending on the characteristics of the global QoS constraints, we solve the resulting planning problem using either a numeric planner Metric-FF \cite{Hoffmann03}, or a temporal-numeric planner we recently developed.

Our new approach has clear advantages. It ensures that a composite service solution can be found if one exists, while existing work may not when no solution within a predefined workflow satisfies the global QoS constraints. Furthermore, our new approach can optimize the overall QoS score, while conventional approaches can only find the optimal QoS score under a given workflow, which may not be globally optimal. The experimental results show that, our new approach significantly extends the capability of prior work by ensuring global satisfiability and optimality without assuming a predefined workflow. We also show that our approach is fast enough for practical deployment, thanks for the highly efficient search engines in state-of-the-art planners.

%paragraph V: The reminder of the paper

The reminder of this paper is organized as follows. Section 2 reviews related work on Web service composition. Section 3 presents problem formulation. In Section 4, we propose a QoS model for a single operation and a composite service. In Section 5, we present our approach to dynamic composition of Web services using planning. Section 6 describes system architecture. Section 7 shows experimental results. Finally, Section 8 concludes the paper and discusses the future work.

\section{Related Work}

Our work is related to QoS-aware Web service composition and automated planning. We first discuss QoS-aware WSC approaches and then review planning-based WSC approaches.

\subsection{QoS-aware Web Service Composition}

Conventional QoS-aware WSC approaches can be classified into four categories: exhaustive search, local optimization, integer programming and approximative algorithm. They all need a predefined workflow, which constrains their solution space. As a result, they are not globally complete or optimal.

\begin{itemize}
\item \textbf{Exhaustive Search}.
This approach tries to enumerate all possible composite service combinations by using candidate services from each task. As a consequence, a composite service solution to a predefined workflow model with the optimal QoS score can be selected, if one exists and satisfies all global QoS constraints. However, the time complexity of this approach is high, i.e., $O(m^p)$, where $m$ and $p$ are, respectively, the maximum number of candidate services for a task and the number of tasks in a workflow model. Thus, this approach is not appropriate for large scale composition problem of Web services.

\item \textbf{Local Optimization}.
This is a local optimal QoS service selection process for Web service composition. A QoS vector is used to represent and measure QoS information of each Web service. After the QoS collection of each candidate service in a predefined workflow model, a Multiple Criteria Decision Making (MCDM) process \cite{El10,Wu07} is applied to compute the QoS score of a Web service, using the weights assigned by a user to each QoS criterion. For each task in a workflow model, the Web service with the optimal QoS score is selected from its candidate services group, as shown in Fig. \ref{fig:qos-candidate-ws}. Although this approach is locally optimal and efficient with a low time complexity, i.e., $O(m*p)$, it does not guarantee to satisfy global QoS constraints when finding a composite service solution.

\item \textbf{Integer Programming}.
Since high complexity makes exhaustive search impractical and local optimization does not take global QoS constraints into account, Zeng \emph{et al.} \cite{Zeng04} proposed a method based on Integer Programming (IP). Based on a predefined workflow model, it transforms a Web service composition problem including global QoS constraints to an IP problem. An IP solver is then used to find an execution plan.

\item \textbf{Approximative Algorithm}.
In order to decrease the time complexity, Zhang \emph{et al.} \cite{Zhang07} models QoS-aware Web service composition problem as a multi-dimensional multi-choice knapsack problem. It still requires a predefined workflow to support service selection. Although it is an NP-complete problem, a heuristic algorithm can be used. The approximative algorithm of constructing the convex hull of related points \cite{Zhang07} has been applied to generate a composite service with a suboptimal overall QoS score.
\end{itemize}

\subsection{Planning-based Web Service Composition}

AI planning has been applied to Web service composition for as long as there have been Web services. For automatic composition of Web services, some approaches use AI search techniques to find a composition solution, such as heuristic forward and regression search \cite{Oh08,Oh07} and planning graph construction \cite{Zheng08}. There are also some approaches \cite{Falou10,Sirin04,Klusch05} that directly use an AI planner to find a solution plan.

In addition to deterministic composition approaches where the initial states and action outcomes are deterministic, there are approaches \cite{Hoffmann09,Hoffmann07,Giacomo09} that take the uncertainty of the initial state into consideration. These approaches transform a WSC problem to a conformant planning problem with multiple possible initial states. However, solving a conformant planning problem is a time-consuming task due to its expensive belief states update \cite{Hoffmann09}.

To the best of our knowledge, our proposed work is original and distinguishes from other existing methods. Although many works have been done on Web service composition using planning, they cannot handle WSC problems with global QoS constraints and preferences. The planning problem for traditional WSC requires only classical planning with propositional logics. In contrast, the planning problem for QoS-aware service composition is more complex. It entails cost-sensitive temporally expressive (CSTE) planning which requires not only logical reasoning, but also temporal reasoning and numeric optimization. We use our recently proposed SAT-based SCP solver to solve this problem.

\section{Problem Formulation}
We first formulate our problem using a simplified model. In this paper, we focus on understanding the fundamental principles of QoS-aware service composition, and omit some other complicating aspects of WSC.

\begin{defi}
\textbf{(Web service)}. A Web service $w$ consists of a set of operations, denoted as $w=\{op_1, op_2, \cdots \}$, where $\forall op \in w$ is a 3-tuple $(I, O, Q)$, where $I=\{I^1,I^2,\cdots \}$ is a  set of input interface parameters, $O=\{O^1,O^2,\cdots \}$ is a set of output interface parameters, $Q=\{Q^1, Q^2, \cdots \}$ is a set of QoS values for a group of QoS criteria. We use $op.I$, $op.O$ and $Q(op)$ to denote $I$, $O$ and $Q$ in $op$, respectively.
\label{def:ws}
\end{defi}

Note that each Web service plays a role that can perform a set of operations. A Web service repository is a set of services. We denote it as $W=\{w_1, w_2, \cdots\}$.

\begin{defi}
\textbf{(Functionality request)}. A functionality request, $r$, is a 2-tuple $(r_{in},r_{out})$, where $r_{in}=\{r_{in}^1,r_{in}^2,\cdots \}$ is an interface parameter set provided as request inputs, and $r_{out}=\{r_{out}^1,r_{out}^2,\cdots \}$ is a goal specification provided as desired results.
\end{defi}

QoS criteria can be divided into two categories: positive and negative. Positive QoS criteria denote better quality with higher values, while negative ones correspond to lower quality with higher values. To simplify our definitions, we directly use a set of numbers to represent lower or upper bound restrictions to QoS criteria, as well as user preferences on QoS criteria.

\begin{defi}
\textbf{(Global QoS constraints)}. Given a group of QoS criteria, global QoS constraints, denoted as $C$, are a set of QoS values $\{c_1, c_2, \cdots \}$. Each element $c \in C$ restricts a global upper or lower bound on a QoS criterion for a composite service.
\end{defi}

\begin{defi}
\textbf{(QoS preferences)}. Given a group of QoS criteria, QoS preferences, denoted as $P$, are a set of QoS weights $\{w_1, w_2, \cdots \}$. Each element $w \in P$ denotes a user preference on a QoS criterion.
\end{defi}

Notice that all the QoS preferences set by a user must satisfy $\sum_{i=1}^{\mid P \mid}w_i=1$, where $0 \leq w_i  \leq 1$.

Given a set of Web services, a functionality request, a set of global QoS constraints and QoS preferences, we define the problem of QoS-driven Web service composition as below.

\begin{defi}
\textbf{(QoS-driven Web service composition)}. A QoS-driven Web service composition, denoted as Q-WSC, is defined by $(W, C, P, r_{in}, r_{out})$. (1) a Web service repository $W=\{w_1, w_2, \cdots\}$, (2) a set of global QoS constraints $C=\{c_1, c_2, \cdots \}$, (3) a set of QoS preferences $P=\{w_1, w_2, \cdots\}$, (4) an input parameter set $r_{in}=\{r_{in}^1,r_{in}^2,\cdots \}$, and (5) a goal specification $r_{out}=\{r_{out}^1,r_{out}^2,\cdots \}$.
\end{defi}

\begin{table}[tp]

\caption{\small Input and output interface parameters of each single operation in a Web service repository. Column $`$Service' is the Web service that an operation belongs to.}
\vspace{-0.4cm}
\begin{center}
\label{table:problem-formulation}

\renewcommand{\arraystretch}{1.3}
\small \setlength{\tabcolsep}{1.0 pt}

\begin{tabular}{|c|c|c|c|} \hline
Operation & Service & $op.I$ & $op.O$ \\ \hline

$op_1$ & $w_1$ & $\{par1, par2\}$ & $\{par3, par4\}$ \\
$op_2$ & $w_1$ & $\{par3\}$ & $\{par5, par6\}$ \\
$op_3$ & $w_1$ & $\{par4\}$ & $\{par7, par8, par9\}$ \\
$op_4$ & $w_2$ & $\{par7, par8, par9\}$ & $\{par10\}$ \\
$op_5$ & $w_2$ & $\{par5, par6, par10\}$ & $\{par11, par12, par13\}$ \\
$op_6$ & $w_3$ & $\{par11, par12\}$ & $\{par14\}$ \\
$op_7$ & $w_3$ & $\{par13\}$ & $\{par15, par16\}$ \\
$op_8$ & $w_3$ & $\{par14, par15, par16\}$ & $\{par17, par18, par19\}$ \\ \hline
\end{tabular}

\end{center}
\vspace{-4mm}
\end{table}

A composition solution to a Q-WSC problem is an ordered sequence of operations extracted from $W$, $\pi=(op_1, op_2, \cdots, op_n)$, such that it not only satisfies both a functionality request and all global QoS constraints, but also optimizes the overall QoS score.

\textbf{Example 1.} Consider a QoS-driven WSC problem $(W, C, P, r_{in}, r_{out})$. For the service repository $W$, it has three services $\{w_1, w_2, w_3\}$, where $w_1=\{op_1, op_2, op_3\}$, $w_2=\{op_4, op_5\}$ and $w_3=\{op_6, op_7, op_8\}$. Table \ref{table:problem-formulation} shows all the operations in $W$, and their input and output parameters. Table \ref{table:qos-composite-service-data} shows five QoS criteria as well as their QoS values for each operation in $W$. Assume that a user submits $C=\{240, 150, 0.40, 0.35, 3.8\}$ as global QoS constraints on the five QoS criteria, as shown in Table \ref{table:qos-composite-service-data}. Also, suppose that the user provides five QoS preferences $P=\{0.25, 0.3, 0.15, 0.2, 0.1\}$, each for a QoS criterion. Finally, an input parameters set $r_{in}=\{par1, par2\}$ and a goal specification $r_{out}=\{par17, par18, par19\}$ are also specified as functionality request.
\hfill $\blacksquare$

\section{QoS Model}
\label{sec:qos-model}

We introduce a QoS model which forms the basis for our approach. Based on widely used QoS measures \cite{Zeng04,Liu04}, we present a general QoS model for both a single operation and a composite service.

\subsection{Single Operation QoS}
There are five nonfunctional properties for a single operation in our QoS model. They are execution price, execution time, invocation rate, availability and reputation.

\begin{itemize}
\item \textbf{Execution Price}.
Given an operation $op$, the execution price $q_{price}(op)$ is the cost that service requesters have to pay for the invocation of $op$, which is published by a service provider. It is calculated by the expression
$$q_{price}(op) = p_{process}(op) + p_{communicate}(op)$$
where $p_{process}$ is the processing fee for the use of $op$ and $p_{communicate}$ is the cost for communication with other operations.

\item \textbf{Execution Time}.
Given an operation $op$, its execution time measures the expected duration between the moment when a service request is sent and the moment when the result is returned to the users or forwarded to other services \cite{Zeng04}. The execution time of an operation $op$ is calculated by the expression
$$q_{time}(op) = t_{process}(op) + t_{communicate}(op)$$
where $t_{process}$ is the processing time of $op$ and $t_{communicate}$ indicates the communication time for a service request and reply when invoking $op$.

\item \textbf{Invocation Rate}.
Given a time slot $[0, \theta]$, the invocation rate $q_{rate}(op)$ of an operation $op$ measures the probability that $op$ can be successfully executed within the period of $\theta$. We calculate the invocation rate of $op$ by the expression
$$q_{rate}(op) = e^{-\int_{0}^{\theta}f_{op}(t)dt}$$
where $f_{op}(t)$ is the distribution function of failure invocation rate of $op$ with time variable $t$. If we set the failure rate as a constant $\phi(op)$, then the invocation rate of $op$ is calculated as
$$q_{rate}(op) = e^{-\phi(op) \ast \theta}$$
The range of the invocation rate is from 0 to 1.

\item \textbf{Availability}.
Given an operation $op$, the availability $q_{avail}(op)$ of $op$ measures the probability that $op$ can be accessible. Its availability value is calculated by the expression
$$q_{avail}(op) = \frac{t_{avail}(op)}{\tau}$$
where $t_{avail}(op)$ is the total time when $op$ is available within a given period of $\tau$. The range of availability is also in $(0, 1]$.

\item \textbf{Reputation}.
Given an operation $op$, the reputation $q_{rep}(op)$ of $op$ measures its trustworthiness by the service requesters. The reputation value is calculated by the average of a group of feedback from end users.
$$q_{rep}(op) = \frac{\sum_{k=1}^{N}Rep_k}{N}$$
where $Rep_{k}$ is the an evaluation value from the $k$th service requester. $N$ is the number of evaluation times. Usually, the reputation of an operation ranges from 1 to 5.
\end{itemize}

Based on the above five QoS criteria, we define a QoS vector $Q(op)$ to model the QoS of an operation $op$.
$$Q(op)=(q_{price}(op), q_{time}(op), q_{rate}(op), q_{avail}(op), q_{rep}(op))$$

\subsection{Composite Service QoS and Global Constraints}

A composite service consists of multiple single operations that are organized by certain partial orders, as shown in Fig. \ref{fig:qos-composite-service}. The overall QoS of a composite service graph is calculated from the QoS of single operations.

Assume that, given a set of global QoS constraints $C=\{c^*(price), c^*(time), c^*(rate), c^*(avail), c^*(rep)\}$ on the QoS criteria, the QoS score of a composite service on each criterion and global constraint are as follows.

\begin{figure}[tp]
    \centering
    \includegraphics[scale=0.68]{figure/qos-composite-service-8.eps}
    \centering
    \caption {\small A composite service graph with 8 operations. Each operation contains a set of QoS values for their corresponding QoS criteria, as shown in Table \ref{table:qos-composite-service-data}.}
\label{fig:qos-composite-service}
\vspace{-0.2cm}
\end{figure}

\begin{itemize}
\item \textbf{Execution Price}.
Given a composite service graph $G$, its execution price $Q_{price}(G)$ is the sum of execution prices of all the operations in $G$. Taking the given global QoS constraint $c^*(price)$ as its upper bound, we have an inequality for the global constraint:
\begin{equation}
\label{global-constraint-price}
\sum_{i = 1}^{N}q_{price}(op_i) \leq c^*(price)
\end{equation}
where $N$ is the number of operations in $G$.

\item \textbf{Execution Time}.
Given a composite service graph $G$, its execution time $Q_{time}(G)$ depends on the maximum span of execution time of operations in $G$. More specifically, it is determined by a directed acyclic path starting from an initial state and ending at a goal state, called \textbf{critical operation path}, which consists of a subset of operations in $G$ such that the sum of their execution time is maximized. That is, it is computed by the expression
$$Q_{time}(G) = \sum_{op_i \in CP}q_{time}(op_i)$$
where $q_{time}(op_i)$ is the execution time of $op_i$, and $op_i$ is an operation in the critical operation path $CP$. For instance, Table \ref{table:qos-composite-service-data} shows each single operation QoS in Fig. \ref{fig:qos-composite-service}, its critical operation path with maximum execution time is $CP=\{ op_1, op_3, op_4, op_5, op_7, op_8 \}$. Based on the given $c^*(time)$ as its upper bound, the global constraint on execution time is
\begin{equation}
\label{global-constraint-time}
\sum_{op_i \in CP}q_{time}(op_i) \leq c^*(time)
\end{equation}

\item \textbf{Invocation Rate}.
Given a composite service graph $G$, its invocation rate $Q_{rate}(G)$ is the product of invocation rates of all the operations in $G$. Using the given global QoS constraint $c^*(rate)$ as a lower bound, the global constraint on invocation rate is
$$\prod_{i=1}^{N}q_{rate}(op_i) \geq c^*(rate)$$
Since the above global constraint is a nonlinear inequality that cannot be easily handled by automated planners, we transform it into a linear global constraint as follows
$$\log_{\frac{1}{2}}\prod_{i=1}^{N}q_{rate}(op_i) \leq \log_{\frac{1}{2}}c^\ast (rate)$$

or equivalently,
\begin{equation}
\label{global-constraint-rate}
\sum_{i=1}^{N}\log_{\frac{1}{2}}q_{rate}(op_i) \leq \log_{\frac{1}{2}}c^\ast (rate)
\end{equation}

\item \textbf{Availability}.
Given a composite service graph $G$, its availability $Q_{avail}(G)$ is the product of availability of all the operations in $G$. Taking $c^*(avail)$ as its lower bound, the global constraint on availability is
$$\prod_{i=1}^{N}q_{avail}(op_i) \geq c^*(avail)$$
Similarly, we can transform it to:
\begin{equation}
\label{global-constraint-avail}
\sum_{i=1}^{N}\log_{\frac{1}{2}}q_{avail}(op_i) \leq \log_{\frac{1}{2}}c^\ast (avail)
\end{equation}

\item \textbf{Reputation}.
Given a composite service graph $G$, its reputation $Q_{rep}(G)$ is the reputation of average operations in $G$. Using $c^*(rep)$ as its lower bound, the global constraint on reputation of $G$ is
\begin{equation}
\label{global-constraint-rep}
\frac{\sum_{i=1}^{N}q_{rep}(op_i)}{N} \geq c^*(rep)
\end{equation}

\end{itemize}

\begin{table}[tp]
\caption{\small Single operation QoS in the composite service graph shown in Fig. \ref{fig:qos-composite-service}. For each single operation, its execution price ranges from 1 to 50, and the execution time is from 1 to 40. Invocation rate and availability are both from 0.75 to 1. The reputation of each single operation ranges from 3.0 to 5.0.}
\begin{center}
\label{table:qos-composite-service-data}

\renewcommand{\arraystretch}{1.3}
\small \setlength{\tabcolsep}{2.7 pt}
\vspace{-0.2cm}
\begin{tabular}{|c|ccccc|} \hline
\multirow{2}{*}{Operation} & Exec. & Exec. & Invocation & \multirow{2}{*}{Availability} & \multirow{2}{*}{Reputation} \\
& Price & Time & Rate & & \\\hline

$op_1$ & 26 & 15 & 0.85 & 0.93 & 4.6 \\
$op_2$ & 34 & 22 & 0.90 & 0.88 & 3.3 \\
$op_3$ & 18 & 36 & 0.84 & 0.89 & 5.0 \\
$op_4$ & 49 & 19 & 0.96 & 0.95 & 3.7 \\
$op_5$ & 37 & 20 & 0.91 & 0.97 & 4.8 \\
$op_6$ & 15 & 11 & 0.98 & 0.86 & 3.1 \\
$op_7$ & 35 & 28 & 0.93 & 0.92 & 3.5 \\
$op_8$ & 19 & 23 & 0.82 & 0.75 & 4.1 \\ \hline
\end{tabular}

\end{center}
\vspace{-6mm}
\end{table}

\textbf{Example 2.} Consider the composite service graph $G$ illustrated in Fig. \ref{fig:qos-composite-service}. Assume that Table \ref{table:qos-composite-service-data} shows the QoS of each operation. Reconsider the global QoS constraints on QoS values in Example 1, where $c^*(price)=240, c^*(time)=150, c^*(rate)=0.40, c^*(avail)=0.35$ and $c^*(rep)=3.8$. The global constraints for $G$ on five QoS criteria are as follows.

\noindent (1) $\sum_{i=1}^{8}q_{price}(op_i)=233 \leq c^*(price) = 240$; \vspace{1mm} \\
(2) $\sum_{op_i \in CP}q_{time}(op_i) =141 \leq c^*(time)=150$; \vspace{1mm} \\
(3) $\sum_{i=1}^{8}\log_{\frac{1}{2}}q_{rate}(op_i)=1.253  \leq \log_{\frac{1}{2}}c^*(rate)=1.322$; \vspace{1mm} \\
(4) $\sum_{i=1}^{8}\log_{\frac{1}{2}}q_{avail}(op_i)=1.328$ $\leq$ $\log_{\frac{1}{2}}${\small $c^*(avail)$} = 1.515; \vspace{1mm} \\
(5) $\frac{\sum_{i=1}^{8}q_{req}(op_i)}{8} = 4.013 \geq c^*(req) = 3.8$; \vspace{1mm}

After checking global constraints on five QoS criteria, the composite service graph $G$ satisfies the global QoS constraints. \hfill $\blacksquare$

\subsection{QoS Normalization and Objective Function}

When calculating an overall QoS score for a single operation, we adopt a weighted sum of QoS criteria values. Since QoS criteria have different ranges, we need to first normalize them.

There are two QoS criteria categories: positive and negative. QoS criteria in the first category, including invocation rate, availability, and reputation, denote better quality with higher values. Since our goal is to minimize the overall QoS score of a composite service, we take an inverse QoS normalization for each operation. For positive QoS criteria, its normalization function is:
$$q_{i}^{j}=
\left\{
\begin{aligned}
& \frac{Q_{i}^{min}}{q_{i}(op_j)}, & \mbox{if} \ \ Q_{i}^{max} \neq Q_{i}^{min}\\
& 1, & \ \mbox{if} \ \ Q_{i}^{max} = Q_{i}^{min}\\
\end{aligned}
\right.
$$

where $q_{i}(op_j)$ and $q_{i}^{j}$ represent, respectively, the QoS values of the $i$th QoS criterion of $op_j$ before and after QoS normalization. $Q_{i}^{max}$ and $Q_{i}^{min}$ are, respectively, the maximum and minimum QoS values of the $i$th QoS criterion among all operations in a Web service repository.

QoS criteria in the negative category, including execution price and execution time, correspond to lower quality with higher values. For negative QoS criteria, we adopt the QoS normalization function
$$q_{i}^{j}=
\left\{
\begin{aligned}
& \frac{q_{i}(op_j)}{Q_{i}^{max}}, & \mbox{if} \ \ Q_{i}^{max} \neq Q_{i}^{min}\\
& 1, & \ \mbox{if} \ \ Q_{i}^{max} = Q_{i}^{min}\\
\end{aligned}
\right.
$$

Given a QoS vector $Q(op)$ of an operation, After QoS normalization, each QoS value ranges from 0 to 1. We use a QoS vector $Q'(op)$ to represent normalized QoS values of an operation
$$Q'(op) = (q'_{price}(op), q'_{time}(op), q'_{rate}(op), q'_{avail}(op), q'_{rep}(op))$$

Once we have $Q'(op)$, the overall QoS score $qos(op)$ of the single operation $op$ can be calculated by a weighted sum of $Q'(op)$
$$qos(op)= \sum_{i=1}^{n}(Q'(op)[i] \ast w_i)$$
where $Q'(op)[i]$ is the $i$th QoS value in the normalized QoS vector. $n$ is the number of QoS criteria in a single operation. $w_i$ represents a user's preference to the $i$th QoS criterion. The weights must satisfy $\sum_{i=1}^{n}w_i = 1$ and $0<w_i<1$. \vspace{1mm}

Given a composite service graph $G$, its overall QoS score $QoS(G)$ is the sum of the QoS scores of all the operations. So we have
$$QoS(G)= \sum_{i=1}^{N}qos(op_i)$$
where $qos(op_i)$ is the overall QoS score of $op_i$.

\textbf{Example 3.} Reconsider the composite service graph $G$ illustrated in Fig. \ref{fig:qos-composite-service}. We use Table \ref{table:qos-composite-service-data} as the original QoS of each operation. After QoS normalization, Table \ref{table:qos-normalized-data} shows the normalized QoS for each operation. The preferences on the five QoS criteria are \{0.25, 0.3, 0.15, 0.2, 0.1\}, as Example 1 illustrates. The overall QoS score of each operation is as follows. \vspace{1mm}

\noindent (1) $qos(op_1) = \sum_{i=1}^{5}Q'(op_1)[i] \ast w_i = 0.631$; \vspace{1mm} \\
(2) $qos(op_2) = \sum_{i=1}^{5}Q'(op_2)[i]  \ast w_i = 0.758$; \vspace{1mm} \\
(3) $qos(op_3) = \sum_{i=1}^{5}Q'(op_3)[i]  \ast w_i = 0.769$; \vspace{1mm} \\
(4) $qos(op_4) = \sum_{i=1}^{5}Q'(op_4)[i]  \ast w_i = 0.778$; \vspace{1mm} \\
(5) $qos(op_5) = \sum_{i=1}^{5}Q'(op_5)[i]  \ast w_i = 0.710$; \vspace{1mm} \\
(6) $qos(op_6) = \sum_{i=1}^{5}Q'(op_6)[i]  \ast w_i = 0.568$; \vspace{1mm} \\
(7) $qos(op_7) = \sum_{i=1}^{5}Q'(op_7)[i]  \ast w_i = 0.796$; \vspace{1mm} \\
(8) $qos(op_8) = \sum_{i=1}^{5}Q'(op_8)[i]  \ast w_i = 0.714$; \vspace{1mm}

The overall QoS score of the composite service graph $G$ is $QoS(G)=\sum_{i=1}^{8}qos(op_i)=5.724$.  \hfill $\blacksquare$

\begin{table}[tp]
\caption{\small Normalized QoS for each operation in the composite service graph illustrated in Fig. \ref{fig:qos-composite-service}. The original QoS for each single operation is shown in Table \ref{table:qos-composite-service-data}.}
\begin{center}
\label{table:qos-normalized-data}

\renewcommand{\arraystretch}{1.3}
\small \setlength{\tabcolsep}{1 pt}
\vspace{-0.6cm}
\begin{tabular}{|c|ccccc|} \hline
\multirow{2}{*}{Operation} & \ \ Exec. \ \ & \ \ Exec. \ \ & Invocation & \multirow{2}{*}{Availability} & \multirow{2}{*}{Reputation} \\
& Price & Time & Rate & & \\\hline

$op_1$ & 0.531 & 0.417 & 0.965 & 0.806 & 0.674 \\
$op_2$ & 0.694 & 0.611 & 0.911 & 0.852 & 0.939 \\
$op_3$ & 0.367 & 1.000 & 0.976 & 0.843 & 0.620 \\
$op_4$ & 1.000 & 0.528 & 0.854 & 0.789 & 0.838 \\
$op_5$ & 0.755 & 0.556 & 0.901 & 0.773 & 0.646 \\
$op_6$ & 0.306 & 0.306 & 0.837 & 0.872 & 1.000 \\
$op_7$ & 0.714 & 0.778 & 0.882 & 0.815 & 0.886 \\
$op_8$ & 0.388 & 0.639 & 1.000 & 1.000 & 0.756 \\ \hline
\end{tabular}

\end{center}
\vspace{-6mm}
\end{table}

Given a Q-WSC problem $(W, C, P, r_{in}, r_{out})$, our goal is to find a composite service graph $G^*$ such that it has the minimum overall QoS score, while all the global QoS constraints on QoS values in $C$ can be satisfied. The objective function is
\begin{equation}
\label{objective-function}
\argmin_{G^* \in G^s}{QoS(G^*)}
\end{equation}
where $G^s$ represents all the possible composite service graph solutions to a Q-WSC problem. Notice that the composite service graph $G^*$ not only needs to satisfy all global QoS constraints, it also must satisfy the functionality request.

\section{Automated Service Composition using SAT-based Temporal Planning}

We develop an approach that can correctly generate a composite service with the optimal QoS score for a Q-WSC problem. Fig. \ref{fig:scp-aprroach} illustrates an overview of our approach on how to solve a Q-WSC problem. It has a couple of major steps. 1) Translate a Q-WSC problem into a cost sensitive temporally expressive (CSTE) planning problem, which is a numeric planning problem with action duration and cost optimization features. 2) Solve the CSTE planning problem by our developed SAT-based cost planning (SCP) solver, which not only takes logic and temporal reasoning into account, but also optimizes the overall QoS score of a composite service. In particular, when we only consider a numeric planning problem without taking global QoS constraints on temporal restriction (e.g., execution time) and global average constraint (e.g., reputation), we solve the numeric planning problem using a numeric planner (e.g., Metric-FF). It first finds a linear solution plan with the optimal QoS score, and then we perform action dependency analysis on the plan to generate a composite dependency graph.

\begin{figure*}[tp]
    \centering
    \includegraphics[scale=0.85]{figure/qos-approach.eps}
    \centering
    \caption {\small Overview of our approach of QoS-driven Web service composition using SAT-based temporal planning.}
\label{fig:scp-aprroach}
\end{figure*}

\subsection{Q-WSC Temporal Planning Translation}

In order to represent a cost sensitive temporally expressive (CSTE) planning problem, we need to initially define a set of QoS numeric variables $V=\{v_1, \cdots, v_m\}$. By using this, a QoS expression can be defined as an arithmetic expression over $V$ and the rational numbers with a set of arithmetic operators $\{+, -, *, /\}$. Based on a QoS expression, we define a QoS numeric constraint and QoS numeric effect as follows.

\nop{Moveover, we divide $V$ into four groups to represent a QoS objective function, QoS numeric constraints and effects, including a QoS objective variable $V\_o$, a set of dynamic QoS score variables $V\_d$, a set of static global QoS constraint variables $V\_g$ and a set of static QoS preference variables $V\_w$. Here, $V\_g$ and $V\_w$ are assigned from global QoS constraints and preferences and take no changes during temporal planning, as opposed to dynamic QoS numeric variables $V\_o$ and $V\_d$.
}

\begin{defi}
\textbf{(QoS numeric constraint)}. Given a set of $V$ and a QoS expression, a QoS numeric constraint is a triple $(v, comp, exp)$, where $v \in V$ is a numeric variable, $exp$ is a QoS expression, and $comp \in \{<, \leq, >, \geq\}$ is a comparative operator.
\label{defi:qos-planning-problem}
\end{defi}

A QoS numeric constraint restricts a numeric variable $v$ to satisfy a QoS expression by a comparative operator. We use QoS numeric constraints to represent numeric restrictions in the precondition of a CSTE action that is defined later.

\begin{defi}
\textbf{(QoS numeric effect)}. Given a set of $V$ and a QoS expression, a QoS numeric effect is a triple $(v, ass, exp)$, where $v \in V$ is a variable, $ass \in \{:=,$ +=$\}$ is an assignment operator, and $exp$ is a QoS expression.
\label{defi:qos-planning-problem}
\end{defi}

A QoS numeric effect updates QoS value of a numeric variable $v$ by assigning or adding the value of a QoS expression. This way, we use a set of QoS numeric effects to represent the changes of QoS numeric variables in the effect of a CSTE action.

\begin{defi}
\textbf{(CSTE action)}. A cost sensitive durative action $a$ is defined by a tuple $(pre, \emph{eff}, \mu, \rho)$, where $pre$ and $\emph{eff}$ are the action precondition and effect, $\mu$ is the action duration and $\rho$ is the action cost.
\label{defi:qos-planning-problem}
\end{defi}

In a CSTE action $a$, its precondition $pre(a)$ consists of a set of QoS numeric constraints and a set of precondition facts, where each fact is an atomic proposition. Similarly, action effect $\emph{eff}(a)$ has a set of QoS numeric effects and a set of effect facts.

\nop{
We now formally define the cost sensitive temporally expressive (CSTE) planning problem.
}

\begin{defi}
\textbf{(CSTE planning problem)}. Given a Q-WSC problem $(W, C, P, r_{in}, r_{out})$, Q-WSC temporal planning translation transforms it into a CSTE planning problem $(V, A, F, s_0, g)$, where $V$ is a set of QoS numeric variables, $A$ is a set of CSTE actions, $F$ is a set of facts, $s_0$ is the initial state, and $g$ is a goal specification with a set of goal facts.
\label{defi:qos-planning-problem}
\end{defi}

\nop{
Given a CST planning problem $\Pi=(I,F,O,G)$, a plan
$P=(p_0,p_1,\dots,p_{n-1})$ is a sequence of action sets, where each action set
$p_t\subseteq O$ indicates the actions executed at time $t$.  $P$ is
a solution plan if there exists a state sequence $S_0, S_1,...,S_n$ satisfying:
a) $S_0=I$;
b) for each action $o_t\in p_t$,  $o_t$ is applicable at time $t$, and $S_{t+1},~S_{t+\rho(o)}$ satisfy $o_t$'s effects;
c) for all $f\in G$, $f_n \in S_n$.
}

Given a Q-WSC problem $(W, C, P, r_{in}, r_{out})$, we translate it into a CSTE planning problem $(V, A, F, s_0, g)$.

\vspace*{0.05in}
\noindent\textbf{QoS numeric variables.} We divide $V$ into four groups to represent an objective QoS score function, QoS numeric constraints and effects.

1) an objective QoS score variable $V\_o$. It represents the overall QoS score by the costs of all the actions in a CSTE planning state.

2) a set of QoS score variables $V\_d$. For each $V\_d[i]$, it represents the overall QoS score for the $i$th QoS criterion in all the operations, which correspond to the CSTE actions in a CSTE planning state.

3) a set of QoS constraint variables $V\_g$. For each $V\_g[i]$, it is transformed from the $i$th global QoS constraint $c_i \in C$.

4) a set of QoS preference variables $V\_w$. For each $V\_w[i]$, it represents the $i$th QoS preference $w_i \in P$.

Since QoS numeric variables $V\_g$ and $V\_w$ are assigned from global QoS constraints and QoS preferences, they are static variables and take no changes during planning, as opposed to dynamic QoS numeric variables $V\_o$ and $V\_d$.

\vspace*{0.05in}
\noindent\textbf{CSTE actions.} For each Web service $w \in W$, we transform each of its operation $op=(I, O, Q)$ into a CSTE action $a=(pre, \emph{eff}, \mu, \rho)$.

For the precondition $pre(a)$:

1) for each input parameter $I^i \in op.I$, we introduce a precondition fact $(yes\ I^i)$ in $pre(a)$. Here, we represent a precondition fact by a predicate $(yes\ ?p)$ which indicates the availability of an input or output parameter $p$ in a CSTE planning state.

2) for each QoS score variable $V\_d[i]$, if it corresponds to a negative QoS criterion by addition (e.g., execution price), we develop a QoS numeric constraint $(V\_g[i], \geq, V\_d[i]$+$Q(op)[i])$ in $pre(a)$; otherwise, if it represents a positive QoS criterion by product (e.g., invocation rate, availability), we introduce a QoS numeric constraint $(V\_g[i], \geq, V\_d[i]$+$\log_{\frac{1}{2}}Q(op)[i])$ in $pre(a)$. \vspace{0.5mm}

For the effect $\emph{eff}(a)$:

1) for each output parameter $O^i \in op.O$, we introduce an effect fact $(yes\ O^i)$ in $\emph{eff}(a)$.

2) for each QoS score variable $V\_d[i]$, if it represents a QoS criterion by addition or average (e.g., execution price, reputation), we develop a QoS numeric effect $(V\_d[i],$ +=$, Q(op)[i])$ in $\emph{eff}(a)$; otherwise, it is a QoS criterion by product (e.g., invocation rate, availability), we introduce $(V\_d[i],$ +=$, \log_{\frac{1}{2}}Q(op)[i])$ in $\emph{eff}(a)$. \vspace{0.5mm}

For the action duration $\mu(a)$:

We set the duration of action $a$ as the QoS value of execution time in $op$. Assume that execution time is the $i$th QoS criterion in $op$, we have $\mu(a)$=$Q(op)[i]$.

For the action cost $\rho(a)$:

1) we set action cost by a weighted sum of normalized QoS values in $op$. Thus, we have $\rho(a)$=$\sum_{i=1}^{n}(Q'(op)[i] \ast V\_w[i])$, where $n$ is the number of QoS criteria in $op$. The weights satisfy $\sum_{i=1}^{n}V\_w[i] = 1$, where $0<V\_w[i]<1$.

2) for the objective QoS score variable $V\_o$, we increase its overall QoS score by action cost $\rho(a)$ after the execution of action $a$. So we introduce a QoS numeric effect $(V\_o,$ +=$, \rho(a))$ in $\emph{eff}(a)$.

\vspace*{0.05in}
\noindent\textbf{Facts.} The facts include all the precondition and effect facts by input and output parameters from every operation $op$ in each Web service $w \in W$. That is, for each input parameter $I^i \in op.I$ or output parameter $O^i \in op.O$, we develop a fact $(yes\ I^i)$ or $(yes\ O^i)$ in the facts $F$.

\vspace*{0.05in}
\noindent\textbf{Initial state.} We set initial state $s_0$ from initial facts and initial QoS values of numeric variables $V$.

1) for each $r_{in}^i \in r_{in}$, we develop an initial fact $(yes\ r_{in}^i)$ in $s_0$.

2) we set the objective QoS score variable $V\_o$ as 0.

3) for each QoS score variable $V\_d[i]$, we set its initial QoS value as 0.

4) for each QoS constraint variable $V\_g[i]$, if it is used to restrict a QoS criterion by product (e.g., invocation rate, availability), we set its initial value as $\log_{\frac{1}{2}}C[i]$; otherwise, its value is initialized as $C[i]$.

5) for each QoS preference variable $V\_w[i]$, we directly set its value as the same with the QoS preference in $P$. That is, we set each $V\_w[i]$ by QoS preference $P[i]$.

\vspace*{0.05in}
\noindent\textbf{Goal specification.} We set $g$ as a set of goal facts. For each goal parameter $r_{out}^i \in r_{out}$, we develop a goal fact $(yes\ r_{out}^i)$ in $g$.

\textbf{Example 4.} Reconsider the QoS-driven WSC problem $(W, C, P, r_{in}, r_{out})$, as shown in Example 1. After Q-WSC temporal planning translation, it is transformed into a CSTE planning problem $(V, A, F, s_0, g)$.

The QoS numeric variables $V$:

1) $\mathcal{V}\_o=\{qos\_total\}$;

2) $\mathcal{V}\_d=\{price\_d, time\_d, rate\_d, avail\_d, rep\_d\}$;

3) $\mathcal{V}\_g=\{price\_g, time\_g, rate\_g, avail\_g, rep\_g\}$;

4) $\mathcal{V}\_w=\{price\_w, time\_w, rate\_w, avail\_w, rep\_w\}$;

After the translation, an operation in $W$ is translated to a CSTE action. We take the operation $op_1$ as an example, its CSTE action $a_1$ is as follows.

For the precondition $pre(a_1)$:

1) precondition facts: $\{(yes\ par1), (yes\ par2)\}$;

2) QoS numeric constraints: $\{(price\_g, \geq, price\_d+26), (rate\_g, \geq, rate\_d+\log_{\frac{1}{2}}0.85), (avail\_g, \geq, avail\_d+\log_{\frac{1}{2}}0.93)\}$;\vspace{0.5mm}

For the effect $\emph{eff}(a_1)$:

1) effect facts: $\{(yes\ par3), (yes\ par4)\}$;

2) QoS numeric effects: $\{(price\_d,$ +=, $26), (rate\_d,$ +=, $\log_{\frac{1}{2}}0.85), (avail\_d,$ +=, $\log_{\frac{1}{2}}0.93), (rep\_d,$ +=, $4.6)\}$;\vspace{0.5mm}

For the action duration $\mu(a_1)$:

It is the QoS value on execution time of the operation $op_1$, so we have $\mu(a_1)$=$15$.

For the action cost $\rho(a_1)$:

1) we set cost $\rho(a_1)$ as the QoS value of operation $op_1$. Thus, we have $\rho(a_1)=\sum_{i=1}^{5}(Q'(op)[i] \ast V\_w[i])=0.631$, where $V\_w[i]$ equals the $i$th QoS preference $P[i]$.

2) overall QoS score: $\{(qos\_total,$ +=, $0.631)\}$;

After the translation, we get 8 CSTE actions in $A=\{a_1, a_2, \cdots, a_8\}$, each of which is transformed from an operation in Example 1.

The facts $F$ consists of all the atomic propositions by input and output parameters of each operation. Thus, we have $F=\{(yes\ par1), (yes\ par2), \cdots, (yes\ par19)\}$.

The initial state $s_0$ consists of five parts:

1) initial facts: $\{(yes\ par1), (yes\ par2)\}$;

2) objective QoS score: $qos\_total=0$;

3) QoS score on criteria: $\{price\_d=0$, $time\_d=0$, $rate\_d=0$, $avail\_d=0$, $rep\_d=0\}$;

4) QoS constraints: $\{price\_g=240$, $time\_g=150$, $rate\_g=1.322$, $avail\_g=1.515$, $rep\_g=3.8\}$;

5) QoS preferences: $\{price\_w=0.25$, $time\_w=0.3$, $rate\_w=0.15$, $avail\_w=0.2$, $rep\_w=0.1\}$;

Finally, goal specification contains a set of goal facts by $r_{out}$, so $g=\{(yes\ par17), (yes\ par18), (yes\ par19)\}$. \hfill $\blacksquare$

Notice that we do not translate QoS numeric constraints on execution time and reputation in the precondition of a CSTE action, because global QoS constraints on these QoS criteria can not be easily handled by a numeric planner (e.g., Metric-FF \cite{Hoffmann03}). We solve them by our developed SAT-based solver that supports temporal reasoning and optimizes the overall QoS score.

\subsection{Generating an Optimal Solution by SCP Solver}

We now formulate CSTE planning problem as an optimization problem with SAT
constraints and multiple QoS constraints, denoted as  QoS-MinCost SAT problem.
Our planning framework follows the bounded SAT solving strategy, originally proposed in
SATPlan~\cite{Kautz92,Kautz96}. We start from a lower bound of the makespan (N=1),
encode the CSTE planning problem as a MinCost SAT instance, either prove it unsatisfiable or solve it optimally (with respect to the MinCost SAT objective) for each makespan, until a solution is found or the search time is out. Note that we set $c^*(time)$ as the upper bound of the makespan. A QoS-MinCost SAT problem is defined as follows.

\begin{defi}
~\label{def:mincost}
\textbf{(QoS-MinCost SAT Problem)}
A QoS-MinCost SAT problem is a tuple $\Phi^c=(U, L, \delta)$, where $U$ is a
set of boolean variables, $L$ is a set of clauses, and $\delta$ is a
set of cost function $\{\delta_{qos}, \delta_{price}, \delta_{rate}, \delta_{avail}, \delta_{req}\}$, where each $\delta_i: U \rightarrow \mathbb{N}$.
A solution to $\Phi^c$ is a variable assignment $\psi$ that minimizes the objective
function:
\[ QoS(\psi) = \sum_{x\in{V}}{\delta_{qos}(x)v_{\psi}(x)},\]
%\hspace{16mm}
subject to: \[v_{\psi}(p)=1,\forall p\in L,\] \\
and multiple global constraints: \\
\begin{align*}
&  \sum_{x\in{V}}{\delta_{price}(x)v_{\psi}(x)} \leq c^*(price);\\
&  \sum_{x\in{V}}{\delta_{rate}(x)v_{\psi}(x)} \leq \log_{\frac{1}{2}}c^*(rate);\\
& \sum_{x\in{V}}{\delta_{avail}(x)v_{\psi}(x)} \leq \log_{\frac{1}{2}}{c^*(avail)};\\
&  \sum_{x\in{V}}{\delta_{req}(x)v_{\psi}(x)} \geq c^*(rep).\\
\end{align*}
\end{defi}

\subsubsection{Transformation of Actions}

In the first step of our SCP framework,% (Algorithm~\ref{overall}),
each cost-sensitive durative action $a$ is converted to two simple
actions and one propositional fact, written as $(a_{\vdash},a_{\dashv},f^a)$.
We use the symbol $o$ to denote the simple action which indicates the
starting ($o = a_{\vdash}$) or ending events ($o = a_{\dashv}$) of $a$. The fact $f^a$, when it is true, indicates that $a$ is being executed. We denote the set of all such
$f^a$ as $F^a=\{ f^a \mid a\in A\}$. We further denote $pre(o)$,
$\emph{eff}(o)$ as the set of preconditions and the set of effects of a simple action $o$, respectively. Note this transformation would only take effects on those actions. Otherwise, the durative action is just a simple action, thus a transformation is not needed.

We transform a CSTE planning problem, denoted as $\Pi=(V, A, F, s_0, g)$, into a
simplified planning problem $\Pi^s=(I, F^s,A^s,G)$, where action set $A^s = \{o_{\vdash},o_{\dashv}\mid o \in O \} \cup
\{\textrm{no-op action} \textrm{ for} f \mid  f \in F^s\}$, $I=s_0$, $G=g$ and $F^s = F\cup
F^o$. The use of no-op actions
is a standard technique for SAT-based planning to handle the frame problem.
A no-op action for $f$ has no delete-effect and uses $f$ as its precondition and add-effect.
The cost of each simple action is defined as,
\[ \rho(o) = \left  \{
\begin{array}{ll}
   \rho(a),    & \mbox{ if $o = a_{\vdash}$ } \\
    0,          & \mbox{otherwise}\\
\end{array} \right. \]

Given the above representation, it is necessary to encode action
mutual exclusion (mutex) constraints to ensure the correctness of
solutions. An algorithm that detects mutexes between actions in planning problems is proposed in~\cite{blum97}.
We use this algorithm to compute mutexes for all transformed actions $o \in A^s$, which are included in the encoding.

\subsubsection{MinCost SAT Encoding}

%After the above transformation,
For a CSTE planning problem $\Pi=(V, A, F, s_0, g)$ and the corresponding transformation $\Pi^s=(I,F^s,A^s,G)$, given a makespan $N$, we define a QoS-MinCost SAT problem $\Phi^c$ with the following variable set $U$ and clause set $L$.
The variable set $U$ includes two types of variables:

\begin{enumerate}
\item action variables $x_{a,t}$,~$0\le t < N,~a\in A^s$.
\item fact variables $x_{f,t}$,~$0\le t \le N,~f\in F^s$.
%\item goal set variables $W_{t}$, $N-\delta+1 \le t \le N$.
\end{enumerate}
Each variable in $U$ represents the assignment of an action or a fact at time $t$.

The clause set $L$ has the following clauses:
\begin{enumerate}
\item Initial state (for all $f\in I$):~$x_{f,0}$. All initial states must be true at time $0$.

\item Goal state (for all $g'\in G$):~$x_{g',N}$. All goal states must be true at time $N$.
%Qiang 3.15 why delete this?
%\item Partial order goal states (for all $t\in[N-\delta+1,N]$):\\
%$W_t \rightarrow \bigwedge_{\forall f\in G} x_{f,t}$

\item Preconditions of simple actions (for all $a\in A^s$,~$0\le t < N$):
$$x_{a,t}\to \bigwedge_{f\in pre(a)}x_{f,t}$$
%$\neg x_{a,t} \begvee x_{f,t}$.\\
If an action is true at time $t$, then its precondition facts must be true at time $t$ as well.

\item Action effects of simple actions (for all $f\in F^s$,~$0 < t \le N$):
$$x_{f,t} \to \bigvee_{\{a \mid f\in \emph{eff}(a)\}} x_{a,t-1}$$
%$\neg x_{f,t} \bigvee_{\forall a, f\in add(a)} x_{a,t-1}$
If a fact $f$ is true at time $t$, then there must exist an action having $f$ as its effect which is true at time $t-1$.

%\item Delete effects of simple actions (for all $a\in O^s$,~$0\le t < N$):
%$$x_{a,t}\to \bigwedge_{\forall f, f\in del(a)} \neg x_{f,t+1}$$
%An action is true at time $t$, then all its delete-effects can't be ture at time $t+1$.

\item Durative actions ($\forall o,t,~o\in A$,~$0\le t < t+\mu < N$):
$$ x_{o_{\vdash},t } \leftrightarrow x_{o_{\dashv},t+\mu-1}$$
$$ x_{o_{\vdash},t} \rightarrow \bigwedge_{t+1 \leq t' \leq t+\mu-1} ( x_{ f^o, t'} )$$
$$ x_{o_{\vdash},t} \rightarrow \bigwedge_{t+1 \leq t' \leq t+\mu-1} ( \bigwedge_{f \in \pi_{\leftrightarrow}} x_{f,t'} )$$
%$ x_{o_{\vdash},t} \rightarrow \bigwedge_{t<t'<t+\rho-1,f\in
%o_{\leftrightarrow}  } x_{ f^o, t'}$
%Qiang ??? not quite understand.
If a start action $o_{\vdash}$ is true at time $t$, then action $o_{\dashv}$ must be true at time $t+\mu-1$, and vice versa.
If a start action $o_{\vdash}$ is true at time $t$, then the fact $f^o$ and all the overall facts determined by $\pi_{\leftrightarrow}$ must be true in the executing duration $[t+1, t+\mu-1]$. These constraints enforce that $o$ is executed in $[t, t+\mu)$.
Note that it is not necessary to encode this type of constraints for those actions whose duration $\mu$ is smaller than or equal to 1.

%\item Axioms (for each $a\in A$,$0\le t\le N$): \\
%    $\bigwedge_{f\in pre(a)}(x_{f,t})\rightarrow \bigwedge_{f'\in \textit{eff}(a)}(x_{f',t})$

\item Action mutexes ($0\le t < N$): for each pair of  mutex actions $(a_1,a_2)$:
    $$\neg x_{a_1,t} \bigvee \neg x_{a_2,t}$$
These clauses indicate that those mutex actions cannot be true at the same time.

\item Fact mutexes ($0\le t \le N$): for each pair of mutex facts $(f_1,f_2)$:
    $$\neg x_{f_1,t} \bigvee \neg x_{f_2,t}$$
These clauses indicate that those mutex facts cannot be true at the same time.
\end{enumerate}

Since the transformed problem is a QoS-based classical numeric planning problem with temporal constraints, the encoding introduced above shares many similarities to the well know STRIPS encoding~\cite{Kautz92} except for clauses in class (5).

The encoding above produces a standard SAT problem.
The cost of each variable $x \in U$ in a QoS-MinCost SAT problem
$\Phi^c=(U,L,\delta)$ is defined as:
\[ \rho(x) = \left  \{
\begin{array}{ll}
   \rho(a),       & \mbox{if $x=x_{a_{{\vdash},t}}$, $a\in A$, $ 0<t \leq c^*(time)$ } \\
    0,          & \mbox{otherwise}\\
\end{array} \right. \]
In other words, for each action $a$ whose cost is $\rho(a)$, we make the
corresponding variable $x_{a_{\vdash},t}$ to have a cost $\rho(a)$. All
other variables have zero costs.


%In this section, we take into account five QoS global constraints.

%Qiang proposed a SAT-based SCP solver, which can solve complex problem with expressively temporal planning and numeric reasoning.

\subsubsection{The BB-DPLL Algorithm for Solving Qos-MinCost SAT Problem}

%***********************************************************************
% *******************  main procedure of BB-DPLL   ************
%***********************************************************************
\begin{algorithm}[t]
\label{bb-dpll}
\LinesNumbered
\caption{ BB-DPLL($\Phi^c$) }

\KwIn{a QoS-MinCost SAT problem $\Phi^c$;}
\KwOut{a solution with minimum QoS score;}

$\tau \leftarrow \infty$\;

$num \leftarrow 0$\;

\While{ $true$ }{
    $conflict \leftarrow$ propagate()\;

    \eIf{$conflict$}{
        $learnt \leftarrow$ analyze($conflict$)\;
        \eIf{$conflict$ is of top-level}{
            return $num > 0$ ? SAT:UNSAT\;
        }{
            add $learnt$ to the clause database\;
            backtrack()\;
        }
    }{

      % $g(\psi) \leftarrow $cost($\psi$) \;

    %    $h(\psi) \leftarrow $cost\_propagate() \;

        \eIf{constraints check failed or $QoS(\psi) \geq \tau$}{
            %pruning() \;
            backtrack()\;
        }{

            \eIf{all variables are assigned}{
                $num$++\;
                $\tau \leftarrow QoS(\psi)$\;
                %update constraint bounds\;
                backtrack()\;
            }{
                decide()\;
            }
        }
    }
}
\end{algorithm}
%*************    End of algorithm   ************************************

\textbf{Algorithm} \ref{bb-dpll} takes a QoS-MinCost SAT problem $\Phi^c$ as input, and use a a branch-and-bound based DPLL~(BB-DPLL) algorithm to find a composite service graph with optimal overall QoS score.

%\ subsection{The DPLL algorithm}
Here we give an overview of the BB-DPLL procedure, which integrates two popular schemes, DPLL and branch-and-bound search procedures.
Many complete SAT solvers are based on the DPLL algorithm~\cite{Davis62,zhang:CAV-02}, along with other techniques
such as clause learning~\cite{Marques96} and constraint propagation~\cite{Moskewicz:DAC-01}.
%Branch-and-bound has been extensively studied and applied to SAT solving~\cite{Planes03,Fu06,Larrosa09}.
%, planning-specific bounding and variable ordering techniques have not been extensively studied before in a SAT solver.
%Branch-and-bound has been extensively studied and applied to SAT solving~\cite{Planes03,Fu06,Larrosa09}.

The BB-DPLL procedure is shown in Algorithm~\ref{bb-dpll}.
%, which was used in the implementation of the MiniSAT solver~\cite{Een:TAST-04}.
The algorithm uses a propagation queue that contains all literals
pending propagation and also contains a representation of the
current assignment. In the procedure, a variable is \emph{free} if
it has not been assigned a value. Initially, all variables are free.

The algorithm repeatedly propagates the literals in the propagation
queue and returns a conflict if there is any (Line 4). Once a
conflict occurs, the procedure analyze() checks the conflict to
generate a learned clause ~\cite{Een:TAST-04} (Line 6); after that, it calls
backtrack() to undo the assignment until exactly one of the literals
in the learned clause becomes unassigned (Line 11). If no conflict
occurs, it checks the current assignment whether it satisfies QoS global constraints and the QoS score is smaller than the QoS score bound~($\tau$)~(Line 13).
It prunes a search node if any QoS global constraint is unsatisfied or the QoS score is larger than $\tau$~(Line 13), or calls decide() to select a free variable, assigns it to be $true$ or $false$, and inserts it into the propagation queue (Line 21).
Then a new iteration takes place.

Each time a satisfying solution is found when there is no free variable any more (Line 16), it updates the QoS score bound and then backtracks~(Line 18-19).
BB-DPLL keeps searching the whole space until all satisfiable solutions are either visited or pruned, in order to find the one that minimizes QoS score, the objective function of the CSTE planning problem. The procedure stops when a top level conflict is found (Line 7-8).

\subsection{Generating an Optimal Solution by Metric-FF}

When we transform a Q-WSC problem $(W,C, P, r_{in}, r_{out})$ into a CSTE planning problem $(V, A, F, s_0, g)$ without taking into account global QoS constraints on temporal and average QoS criteria, it is a \textbf{numeric planning problem} and we take a numeric planner to find a solution.

\subsubsection{Finding a Linear Solution Plan}

A \textbf{numeric planning problem} is a CSTE planning problem $(V, A, F, s_0, g)$, except that, 1) there are no QoS constraints on temporal and average QoS criteria in $s_0$ (e.g., execution time, reputation), and 2) every action $a \in A$ is a \textbf{numeric action}.

\begin{defi}
\textbf{(Numeric action)}.
A numeric action $a=(pre, \emph{eff}, \rho)$ is a CSTE action without action duration. The precondition is $pre(a)=(p(pre), q(pre))$, where $p(pre)$ is precondition facts and $q(pre)$ is QoS numeric constraints. The effect is $\emph{eff}(a)=(p(\emph{eff}), q(\emph{eff}))$, where $p(\emph{eff})$ is effect facts and $q(\emph{eff})$ is QoS numeric effects.
\end{defi}

In the solution space of a numeric planning problem, a \textbf{numeric planning state} is $S = (S_p, S_q)$, where $S_p = \{(yes\ p_1), (yes\ p_2), \cdots \}$ is a fact state with a set of facts, $S_q=\{V\_d[1], V\_d[2], \cdots, V\_o \}$ is a numeric state with a set of QoS scores on QoS criteria and an objective QoS score. A numeric action $a$ can be applicable to a numeric planning state $S$ as below.

\begin{defi}
\textbf{(Applicability)}.
A numeric action $a=(pre, \emph{eff}, \rho)$ can be applicable to $S$, if all precondition facts in $p(pre)$ are subsumed in $S$ (i.e., $p(pre) \subseteq S_p$), and QoS numeric constraints in $q(pre)$ are satisfied by applying QoS values in $S_q$ (i.e., $V\_d[1], V\_d[2], \cdots$) to $q(pre)$.
\end{defi}

When a numeric action $a$ is applicable to a state $S$, the resulting planning state is $S'=S \oplus a$, where $S'_p=S_p \cup p(\emph{eff})$, and $S'_q=S_q \rhd q(\emph{eff})$, meaning that the QoS values of numeric variables in $S'_q$ are updated by applying the QoS values in $S_q$ to QoS numeric effects in $q(\emph{eff})$.

An \textbf{execution sequence}, $L=(a_1, \cdots, a_m)$, is an ordered list of numeric actions. Applying a sequence $L$ to a numeric planning state $S$ results in a new state $S'=S \oplus L = (((S \oplus a_1) \oplus a_2) \cdots \oplus a_m)$ if every step is applicable (otherwise $S \oplus L$ is undefined).

\begin{defi}
\textbf{(Proposition satisfiability)}. Given a numeric planning state $S=(S_p, S_q)$, an execution sequence $L=(a_i, a_j, \cdots, a_k)$, and a proposition specification $g=\{(yes\ p_1), (yes\ p_2), \cdots \}$, if $S'=S \oplus L$ is defined and $g \subseteq S'_p$, we denote it as $(a_i \otimes a_j \otimes \cdots \otimes a_k) \propto (S \rightarrow g)$, where $1 \leq i, j, k \leq |L|$.
\label{def:satisfiability-plan}
\end{defi}

\begin{defi}
\textbf{(Linear solution plan)}. Given a numeric planning problem $(V, A, F, s_0, g)$, a linear solution plan is an execution sequence, $\pi=(a_i, a_j, \cdots, a_k)$, such that $(a_i \otimes a_j \otimes \cdots \otimes a_k) \propto (s_0 \rightarrow g)$.
\label{def:solu-plan}
\end{defi}

An \textbf{optimal solution plan}, $\pi^*=(a_i, a_j, \cdots, a_k)$, is a linear solution plan with the minimum objective QoS score. That is, after applying actions in $\pi^*$ to the initial state $s_0$, we generate a numeric planning state $S^*=s_0 \oplus \pi^*$, and the objective QoS score in $S^*_q$ (i.e., $V\_o$) is minimized among all feasible linear solution plans.

Any numeric planner that supports PDDL 2.1 and up (e.g. Metric-FF \cite{Hoffmann03}) can be applied to solve our defined QoS-driven numeric planning problem.

\textbf{Example 5.} Reconsider the QoS-driven WSC problem $\{W, C, P, r_{in}, r_{out}\}$, as shown in Example 1. Here, we only consider global QoS constraints $C=(240, 0.40, 0.35)$ on execution price, invocation rate and availability. After Q-WSC temporal planning translation, we generate a numeric planning problem $(V, A, F, s_0, g)$, as shown in Example 4, except that there are no QoS constraints on execution time and reputation in $s_0$, and no duration in each numeric action in $A$. We then use Metric-FF \cite{Hoffmann03} to solve it and find an optimal solution plan, as shown in Fig. \ref{fig:linear-plan}. The solution plan satisfies: $(a_1 \otimes a_3 \otimes a_4 \otimes \cdots \otimes a_8) \propto (s_0 \rightarrow g)$, where $s_0$ and $g$ are the initial state and goal specification.
\hfill $\blacksquare$

\begin{figure}[tbp]
    \centering
    \includegraphics[scale=0.72]{figure/linear-soln.eps}
    \centering
    \caption {\small The linear solution plan with optimal overall QoS score found by Metric-FF. Each numeric action $a_i$ corresponds to an operation $op_i$ in the Q-WSC problem in Example 1.}
\label{fig:linear-plan}
\vspace{-0.2cm}
\end{figure}

\subsubsection{Constructing a Composite Dependency Graph}

A linear solution plan only provides a sequential order among numeric actions, instead of parallel numeric actions that may exist in a solution plan. Thus, we convert it into a composite dependency graph which includes both sequential and parallel order among numeric actions within a solution plan.

\begin{defi}
\textbf{\emph{(Action dependency)}}.
Given a numeric planning problem $(V, A, F, s_0, g)$, and a linear solution plan $\pi=(a_1, \cdots, a_m)$, a numeric action $a_j$ depends on $a_i$ (denoted as $a_i \vdash a_j$), if and only if $i <j$ and there exists at least one precondition fact $f \in p(pre)$ in $a_j$ such that $f \notin s_0$ and $a_i$ is the last action in $a_1, \cdots, a_{j-1}$ such that $f \in p(\emph{eff})$ in $a_i$.
\end{defi}

By performing action dependency on a linear solution plan, we can construct a composite dependency graph.

\begin{defi}
\textbf{\emph{(Composite dependency graph)}}.
Given a linear solution plan $\pi=(a_1, \cdots, a_m)$, the composite dependency graph is a directed acyclic graph $G=(V, E)$, such that $V=\pi$ and there is an edge $(a_i, a_j) \in E$ if and only if $a_j$ depends on $a_i$ $ (a_i \vdash a_j)$.
\label{defi:dg}
\end{defi}

From the above definition, a composite dependency graph describes the invocation order of numeric actions sequentially and in parallel. Each vertex in $G$ is a numeric action $a$. Each edge $(a_i, a_j)$ in $G$ represents an action dependency, in which $a_i$ sends messages to $a_j$ who receives the messages for use.

Given a $(V, A, F, s_0, g)$ and a linear solution plan $\pi$, the procedure composite\_dependency\_graph() tries to construct a composite dependency graph $G$.

\vspace{-2.5mm}
\begin{algorithm}[htbp]
\label{alg:compo-graph-main}
\LinesNumbered \caption{composite\_dependency\_graph($\pi$, $s_0$, $g$)}
\KwIn{a linear solution plan $\pi$; an initial numeric planning state $s_0$; a goal specification $g$;}
\KwOut{a composite dependency graph $G$;}

$G(V) \leftarrow \pi$\;
$G(E) \leftarrow \{\}$\;

\ForEach{$a \in G(V)$} {
    $visited[a] \leftarrow false$\;
}

composite\_edges($s_0$, {\em Start}, $\{\}$, $\{\}$)\;

\textbf{return} $G$\;
\end{algorithm}
\vspace{-2.5mm}

In Algorithm \ref{alg:compo-graph-main}, we first directly collect all numeric actions in $\pi$ as the vertex set $G(V)$. Then, for each vertex $a$ in $G(V)$, we mark it not visited. Starting from an initial numeric planning state $s_0$, we call a recursive procedure composite\_edges() to generate edges $G(E)$. We create an artificial action {\em Start} to serve as the beginning in $G$.

Each call to composite\_edges() in Algorithm \ref{alg:compo-graph-edges} works as follows. We first choose a set of actions applicable to the current numeric planning state $S$ (Line 2). Specifically, for each numeric action $a$ in $G(V)$, if it is not visited and its precondition facts can be satisfied by $S$ (i.e., $p(pre) \subseteq S_p$), we put it into $\mathcal{F}$ as an applicable action (see Algorithm \ref{alg:compo-graph-actions}). After choosing applicable numeric actions in $\mathcal{F}$, there are two possibilities.

(1) If $\mathcal{F}$ has at least one applicable numeric action for $S$, for each action $a_r \in \mathcal{F}$, we first update the current numeric planning state $S$ by adding the effect facts of $a_r$, mark $a_r$ as a visited action, create a new edge into $G(E)$ from $a_l$ to $a_r$ (Lines 3-7), and then recursively call composite\_edges() using the updated numeric planning state $S$ and new left vertex $a_r$ (Line 8).

(2) The second possibility is that there is no such numeric action applicable to the current numeric planning state $S$. In such case, we first update the facts in the combination numeric planning state $S'$ by the current state $S$ and also append $a_l$ to combination actions set $A'$ (Line 10). Then, we try to find an applicable numeric action using $S'$ (Line 11). If no such action can be found (Line 12), we return to the previous numeric planning state $S$ and choose another applicable action to recursively find composite edges (Lines 4-8). Otherwise, we find an action $a_c$ applicable to $S'$ (Lines 13-19). We first update $S$ by combining $S'$ with the effect facts of $a_c$, and mark $a_c$ as a visited action (Lines 14-15). Then, we create a set of new edges from each combination action $a'$ to $a_c$ (Lines 16-17). Finally, we clear $S'$ and $A'$ and recursively call composite\_edges() with the updated planning states and left vertex $a_c$ (Lines 18-19).

%\vspace{-2.5mm}
\begin{algorithm}[htbp]
\label{alg:compo-graph-edges}
\LinesNumbered \caption{composite\_edges($S$, $a_l$, $S'$, $A'$)}
\KwIn{a numeric planning state $S$; a left vertex $a_l$ in a new edge; a combination numeric planning state $S'$; a set of combination actions $A'$;}
\KwOut{a set of composite edges $G(E)$;}

\lIf{$g \subseteq S_p$} {
    \textbf{return}\;
}

$\mathcal{F} \leftarrow$ choose\_actions($S$)\;

\If{$\mathcal{F}$ has applicable actions} {
    \ForEach{$a_r \in F$} {
        $S_p \leftarrow S_p \cup p(\emph{eff})$\;
        $visited[a_r] \leftarrow true$\;
        $G(E) \leftarrow G(E) \cup \{(a_l, a_r)\}$\;
        composite\_edges($S$, $a_r$, $S'$, $A'$)\;
    }
}
\Else {
    $S'_p \leftarrow S'_p \cup S_p$; $A' \leftarrow A' \cup \{a_l\}$\;
    $\mathcal{F}' \leftarrow$ choose\_actions($S'$)\;
    \lIf{$\mathcal{F}'=\{\}$} {
        \textbf{return}\;
    }
    \ElseIf{$\mathcal{F}'$ has an applicable action $a_c$} {
        $S_p \leftarrow S'_p \cup p(\emph{eff})$\;
        $visited[a_c] \leftarrow true$\;
        \ForEach{$a' \in A'$} {
            $G(E) \leftarrow G(E) \cup \{(a', a_c)\}$\;
        }
        $S' \leftarrow \{\}$; $A' \leftarrow \{\}$\;
        composite\_edges($S$, $a_c$, $S'$, $A'$)\;
    }
}
\end{algorithm}
%\vspace{-2.5mm}

%\vspace{-2.5mm}
\begin{algorithm}[htbp]
\label{alg:compo-graph-actions}
\LinesNumbered \caption{choose\_actions($S$)}
\KwIn{a numeric planning state $S$;}
\KwOut{a set of applicable numeric actions in $\mathcal{F}$;}

$\mathcal{F} \leftarrow \{\}$\;

\ForEach{$a \in G(V)$} {
    \If{$visited[a]=false$ \emph{and} $p(pre) \subseteq S_p$} {
        $\mathcal{F} \leftarrow \mathcal{F} \cup \{a\}$\;
    }
}

\textbf{return} $\mathcal{F}$\;
\end{algorithm}
%\vspace{-2.5mm}

\textbf{Example 6:} Reconsider the linear solution plan $\pi$, as shown in Fig. \ref{fig:linear-plan}. The initial state $s_0$ and goal specification $g$ are specified in Example 5. After performing action dependencies on $\pi$, Fig. \ref{fig:compo-dg} illustrates the generated composite dependency graph, in which a numeric action $a_i$ corresponds to an operation $op_i$ in Example 1. Therefore, once a linear solution plan is converted to a composite dependency graph, we can directly map it to a composite service graph, as shown in Fig. \ref{fig:qos-composite-service}.
\hfill $\blacksquare$

\begin{figure}[tbp]
    \centering
    \includegraphics[scale=0.68]{figure/compo-den-graph.eps}
    \centering
    \caption {\small The composite dependency graph for the linear solution plan shown in Fig. \ref{fig:linear-plan}.}
\label{fig:compo-dg}
\vspace{-0.1cm}
\end{figure}

\section{System Architecture}

The framework of our proposed QoS-driven dynamic composition of Web services using temporal planning is illustrated in Fig. \ref{fig:qos-arch}. There are six main components in the system architecture, including domain translator, problem translator, Web service repository (a set of Web services and their corresponding QoS repository), a numeric planner (e.g., Metric-FF), SCP solver and composite dependency mapper. In addition, service requesters can submit their composition requests to the system.

We first translate Web services and their QoS values in QoS repository to a CSTE planning domain in PDDL by domain translator. Then, when a service requester submits a QoS-driven composition request, we translate its functionality request, global QoS constraints and QoS preferences to a CSTE planning problem in PDDL by problem translator. Based on a generated CSTE planning problem that consists of a PDDL domain and PDDL problem, we then take SCP solver to find a composite solution with the optimal overall QoS score. Notice that, a composition solution found by SCP solver can be directly transformed into a composite service graph, as SCP solver can handle cost sensitive temporal planning problem that considers the invocation order of actions sequentially and in parallel. In particular, when the users do not consider global QoS constraints on temporal and average QoS criteria (e.g., execution time, reputation), we first use a numeric planner (e.g., Metric-FF) to find a linear solution plan with the optimal overall QoS score, which then can be extracted to a composite dependency graph by composite dependency mapper.

\begin{figure}[tbp]
    \centering
    \includegraphics[scale=0.47]{figure/qos-architecture.eps}
    \centering
    \caption {\small The system architecture of QoS-driven dynamic composition of Web services using SAT-based temporal planning.}
\label{fig:qos-arch}
\vspace{-0.2cm}
\end{figure}

\section{Experimental Evaluation}

\subsection{Experimental Setup and Datasets}

Experiments are conducted on a DELL PC with Intel Dual Core 3.1 GHZ CPU and 4G RAM. We use Eclipse IDE as the development platform and Java as the programming language to implement all the modules in our system architecture. We implemented the IP-based approach \cite{Zeng04} by automatically generating AMPL model and data from Web service repositories with QoS information. The metric-based planner Metric-FF \cite{Hoffmann03} and our proposed SAT-based SCP solver are integrated in our prototype system. IP-based approach and our approach using Metric-FF are tested on Windows Vista, while SCP solver is run on Ubuntu 11.04.

We have conducted extensive experiments on 30 Web service repositories. Table \ref{table:exp-serv-repos} shows the number of operations in each of these Web service repositories. They are from 6 simulated predefined workflow models with the number of tasks 9, 16, 18, 7, 14 and 20, respectively. By using our developed module called \emph{Q-services generator} for automatically generating randomly specified number of operations, every workflow model corresponds to 5 Web service repositories. Every Web service repository is generated by the number of 5, 10, 15, 20 and 25 candidate operations for each task within its corresponding workflow model, as well as randomly adding certain number of operations that are outside of the workflow model.

For QoS information, we simulated 5 QoS criteria for each single operation, including execution price, execution time, invocation rate, availability and reputation. The module \emph{Q-services generator} is also applied to randomly generate 5 QoS values for each operation. The QoS value scope of an operation in a Web service repository associated with the number of workflow tasks 9, 16 and 18 is restricted to \{5-100, 1-50, 0.65-1, 0.65-1, 3.5-5\} on each five QoS criteria. On the other hand, we have QoS value scope \{5-50, 1-15, 0.65-1, 0.65-1, 3.5-5\} for all the operations in a Web service repository associated with the number of workflow tasks 7, 14 and 20.

\begin{table}[tp]
\caption{\small The 30 Web service repositories tested on Metric-FF, SCP solver and IP-based approach. $`$WO' represents the number of operations covered by tasks defined in a workflow model. $`$TO' is the total number of operations in a Web service repository.}
\vspace{-5mm}
\begin{center}
\label{table:exp-serv-repos}

\renewcommand{\arraystretch}{1.8}
\small \setlength{\tabcolsep}{4.2 pt}

\footnotesize
\begin{tabular}{|c|cc|cc|cc|cc|cc|} \hline
Tasks & \multicolumn{2}{c|}{5} &\multicolumn{2}{c|}{10} & \multicolumn{2}{c|}{15} & \multicolumn{2}{c|}{20} & \multicolumn{2}{c|}{25} \\ \cline{2-11}
No. & WO & TO & WO & TO & WO & TO & WO & TO & WO & TO \\ \hline

9 & 45 & 55 & 90 & 110 & 135 & 165 & 180 & 220 & 225 & 275 \\
16 & 80 & 90 & 160 & 180 & 240 & 270 & 320 & 360 & 400 & 450 \\
18 & 90 & 100 & 180 & 200 & 270 & 300 & 360 & 400 & 450 & 500 \\ \hline \hline
7 & 35 & 45 & 70 & 90 & 105 & 135 & 140 & 180 & 175 & 225 \\
14 & 70 & 80 & 140 & 160 & 210 & 240 & 280 & 320 & 350 & 400 \\
20 & 100 & 115 & 200 & 230 & 300 & 345 & 400 & 460 & 500 & 575 \\ \hline
\end{tabular}

\end{center}
\vspace{-4mm}
\end{table}

\subsection{Experimental Results}

The 30 Web service repositories are classified into two groups for testing the overall QoS score of a composite service solution found by our approach and IP-based approach \cite{Zeng04}. The first group consists of 15 Web service repositories associated with the number of workflow tasks 9, 16 and 18, respectively. They are used to test our approach using Metric-FF (called Metric-FF) and IP-based approach (called IP-Linear) with three global QoS constraints in each composition request. The second group of 15 Web service repositories associated with the number of workflow tasks 7, 14 and 20 are applied to our approach using SCP solver (called SCP-Solver) and IP-based approach (called IP-SAT) with five global QoS constraints in each composition request.

\begin{table*}[tp]
\tiny
\caption{\small Global QoS constraints within a composition request on each Web service repository. Three QoS values are specified within a global QoS constraint for each Web service repository associated with the workflow tasks 9, 16 and 18. There are five QoS values specified within a global QoS constraint for a Web service repository associated with the workflow tasks 7, 14 and 20, respectively.}
\begin{center}
\label{table:exp-qos-constraints}

\renewcommand{\arraystretch}{1.8}
\setlength{\tabcolsep}{2.0 pt}
\newcommand{\minitab}[2][l]{\begin{tabular}{#1}#2\end{tabular}}

\footnotesize
\begin{tabular}{|c|c|c|c|c|c|} \hline
\multirow{2}*{\minitab[c]{Tasks \\ No.}} & \multicolumn{5}{c|}{Global QoS constraints} \\ \cline{2-6}
& 5 & 10 & 15 & 20 & 25 \\ \hline

9 & \{209,0.228,0.274\} & \{176,0.275,0.255\} & \{183,0.289,0.240\} & \{192,0.295,0.281\} & \{163,0.225,0.299\} \\
16 & \{416,0.032,0.038\} & \{372,0.047,0.042\} & \{359,0.042,0.078\} & \{406,0.191,0.074\} & \{348,0.179,0.102\} \\
18 & \{409,0.052,0.063\} & \{362,0.049,0.136\} & \{417,0.055,0.087\} & \{348,0.122,0.079\} & \{394,0.063,0.087\} \\  \hline \hline
7 & \{146,58,0.196,0.291,4.15\} & \{127,39,0.209,0.253,4.15\} & \{90,64,0.257,0.206,3.9\} & \{138,43,0.291,0.235,4.4\} & \{105,82,0.248,0.289,4.35\} \\
14 & \{378,90,0.099,0.090,4.2\} & \{350,102,0.079,0.148,4.3\} & \{279,116,0.128,0.115,4.05\} & \{248,109,0.104,0.074,4.25\} & \{215,80,0.147,0.141,4.26\} \\
20 & \{459,178,0.067,0.074,4.25\} & \{364,161,0.073,0.052,4.10\} & \{462,170,0.078,0.084,3.95\} & \{397,150,0.075,0.052,4.0\} & \{482,162,0.072,0.081,4.17\} \\ \hline
\end{tabular}

\end{center}
\vspace{-2mm}
\end{table*}

\begin{table*}[tp]
\caption{\small Experimental results on overall QoS score of a composite service solution to a composition request by Metric-FF, SCP-Solver and IP-based approach. A global QoS constraint $C_p^m$ is specified in a composition request for the Web service repository associated with the number of $p$ workflow tasks and $m$ candidate operations for each task. Column $`$FF' represents the overall QoS score of a composite service found by Metric-FF. Column $`$SCP' represents the overall QoS score of a composite service by SCP-Solver.}
\begin{center}
\label{table:exp-qos-score}

\renewcommand{\arraystretch}{1.8}
\small \setlength{\tabcolsep}{0.9 pt}

\newcommand{\minitab}[2][l]{\begin{tabular}{#1}#2\end{tabular}}

\footnotesize
\begin{tabular}{|c|c|cc|c|cc|c|cc|c|cc|c|cc|} \hline
\multirow{3}*{\minitab[c]{Tasks \\ No.}} & \multicolumn{3}{c|}{5} & \multicolumn{3}{c|}{10} & \multicolumn{3}{c|}{15} & \multicolumn{3}{c|}{20} & \multicolumn{3}{c|}{25} \\ \cline{2-16}

& \multirow{2}{*}{Constraint} & \multicolumn{2}{c|}{QoS score} & \multirow{2}{*}{Constraint} & \multicolumn{2}{c|}{QoS score} & \multirow{2}{*}{Constraint} & \multicolumn{2}{c|}{QoS score} & \multirow{2}{*}{Constraint} & \multicolumn{2}{c|}{QoS score} & \multirow{2}{*}{Constraint} & \multicolumn{2}{c|}{QoS score} \\ \cline{3-4} \cline{6-7} \cline{9-10} \cline{12-13} \cline{15-16}

& & FF & IP-Linear & & FF & IP-Linear & & FF & IP-Linear  & & FF & IP-Linear & & FF & IP-Linear \\ \hline

9 & $C_9^5$ & 4.301 & 5.479 & $C_9^{10}$ & 4.329 & 5.420 & $C_9^{15}$ & 4.279 & 5.312 & $C_9^{20}$ & 4.149 & 5.155 & $C_9^{25}$ & 4.135 & 4.819 \\
16 & $C_{16}^5$ & 7.950 & 10.279 & $C_{16}^{10}$ & 7.426 & 8.754 & $C_{16}^{15}$ & 7.599 & 8.678 & $C_{16}^{20}$ & 6.971 & 8.782 & $C_{16}^{25}$ & 7.091 & 8.483 \\
18 & $C_{18}^5$ & 9.112 & 11.176 & $C_{18}^{10}$ & 8.740 & 10.160 & $C_{18}^{15}$ & 9.130 & 10.110 & $C_{18}^{20}$ & 7.894 & 9.613 & $C_{18}^{25}$ & 8.494 & 9.789 \\ \hline \hline
No. & Constraint & SCP & IP-SAT & Constraint & SCP & IP-SAT & Constraint & SCP & IP-SAT & Constraint & SCP & IP-SAT & Constraint & SCP & IP-SAT \\ \hline
7 & $C_7^5$ & 3.062 & 4.509 & $C_7^{10}$ & 2.965 & 4.159 & $C_7^{15}$ & 2.708 & 3.837 & $C_7^{20}$ & 3.260 & 3.877 & $C_7^{25}$ & 3.511 & 3.780 \\
14 & $C_{14}^5$ & 6.626 & 8.384 & $C_{14}^{10}$ & 6.624 & 8.230 & $C_{14}^{15}$ & 6.455 & 7.706 & $C_{14}^{20}$ & 6.074 & 7.815 & $C_{14}^{25}$ & 5.955 & 7.499 \\
20 & $C_{20}^5$ & 9.754 & 12.046 & $C_{20}^{10}$ & 10.109 & 11.962 & $C_{20}^{15}$ & 10.038 & 11.320 & $C_{20}^{20}$ & 9.430 & 10.973 & $C_{20}^{25}$ & 9.545 & 11.021 \\ \hline
\end{tabular}

\end{center}
\vspace{-2mm}
\end{table*}

We take 15 composition requests on the first group 15 Web service repositories. For each composition request, it has a global QoS constraint with three QoS values in order on execution price, invocation rate and availability. On the other hand, we take another 15 composition requests on the second group 15 Web service repositories and each of them has a global QoS constraint with five QoS values in order on execution price, execution time, invocation rate, availability and reputation. Table \ref{table:exp-qos-constraints} shows these 30 global QoS constraints, each of which corresponds to a Web service repository. For simplicity, we set QoS preferences $P=\{0.2, 0.2, 0.2, 0.2, 0.2\}$ on five QoS criteria for each composition request. After Q-WSC numeric planning translation, each Q-WSC problem is converted to a numeric planning problem that is fed to Metric-FF and SCP solver to find a composite service solution. We also transform a corresponding Q-WSC problem to an IP problem with AMPL\footnote{AMPL is a comprehensive and powerful algebraic modeling language for linear and nonlinear optimization problems, in discrete or continuous variables.} description and then apply an IP solver (e.g., CPLEX and Gurobi) to find a composite service. Table \ref{table:exp-qos-score} summarizes the overall QoS score of each composite service found by Metric-FF, SCP solver and IP-based approach, respectively.

It is evident from the experimental results that, without an exception, our approach using Metric-FF and SCP-Solver can outperform IP-based approach on the overall QoS score of each composite service solution.

\subsection{Experimental Analysis}

Based on the experimental results, we again distinguish our approach from conventional methods for QoS-aware dynamic composition of Web services.

(1) Our proposed approach using planning and satisfiability does not depend on a predefined workflow model when solving a QoS-aware service composition problem. However, conventional approaches are based on a predefined workflow and then select a sequence of Web services for the tasks defined in that workflow.

(2) From the above experimental results, we conclude that our approach using Metric-FF can always find a composite service with an optimal overall QoS score. But IP-based approach using an IP solver can only find a composite service within those covered by a predefined workflow model. That is, it does not make sure a composite service found by IP-Linear has an optimal overall QoS score in a Web service repository.

(3) In order to deal with global QoS constraints with execution time and reputation, we use SCP solver to handle complex problems with features of expressively temporal planning and numeric reasoning. As shown in the experimental results, the overall QoS score of a composite service solution found by our approach using SCP solver is always better than that of a composite service found by IP-SAT.

(4) Due to the process of dynamically finding a composite service, the computation cost of our approach is slower than IP-based approach. Our approach using Metric-FF can find a linear solution plan within 0.70 second for each composition request. For more complex problems with temporal numeric planning, SCP solver can find a composite service graph within 3.89 seconds. For IP-based approach, its computation cost for finding a composite service solution to each composition request is no more than 0.421 second by an IP solver, CPLEX or Gurobi. Although the computation cost of our approach is slightly slower than IP-based approach, we can still respond to a user within a short period of time.

\section{Conclusions}

Automated and efficient QoS-aware Web service composition will simplify the implementation of business processes and optimize the quality of a composite service. This paper presents a planning-based method for QoS-driven dynamic composition of Web services and proposes a number of novel techniques, including numeric planning translation for Q-WSC problem, dependency analysis of composite service graph, and expressively temporal planning and numeric reasoning.

The method first models a Q-WSC problem with multiple global QoS constraints as a numeric planning problem. Then, the method applies metric-based planner Metric-FF on a numeric planning problem without expressively temporal feature to find an optimal solution plan, which is subsequently transformed to a composite dependency graph by performing dependency analysis between actions. Finally, the method proposes a SAT-based solver that can handle a numeric planning problem with temporal feature and directly find a composite service with optimal overall QoS score. We have conducted extensive experiments on 30 Web service repositories. The extensive experimental results show that our approach can outperform the most efficient IP-based approach in its overall QoS score of a composite service solution, while corresponding to a composition task within a short period of time.

\appendices

\nop{
\section{}
Appendix two text goes here.
}

\ifCLASSOPTIONcompsoc
  \section*{Acknowledgments}
\else
  \section*{Acknowledgment}
\fi

This work was supported by an NSF grant IIS-0713109 and a Microsoft Research New Faculty Fellowship.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\bibliographystyle{IEEEtran}
\bibliography{qos-wsc-bib}

\nop{
\begin{IEEEbiography}{Guobing Zou}
Biography text here.
\end{IEEEbiography}

\begin{IEEEbiography}{Yixin Chen}
Biography text here.
\end{IEEEbiography}

\begin{IEEEbiographynophoto}{Qiang Lu}
Biography text here.
\end{IEEEbiography}

\begin{IEEEbiographynophoto}{Ruoyun Huang}
Biography text here.
\end{IEEEbiography}

\begin{IEEEbiographynophoto}{You Xu}
Biography text here.
\end{IEEEbiography}

\begin{IEEEbiographynophoto}{Yang Xiang}
Biography text here.
\end{IEEEbiography}
}

%\vfill
%\enlargethispage{-5in}

\end{document}



